package previous.Test_0127;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //前缀
    //和为k的子数组

    public int subarraySum2(int[] nums, int k) {
          Map<Integer,Integer> hash=new HashMap<Integer, Integer>();
          int n=nums.length;
          hash.put(0,1);
          int sum=0,ret=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            ret+=hash.getOrDefault(sum-k,0);
            hash.put(sum,hash.getOrDefault(sum,0)+1);
        }
        return ret;
    }
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> hash=new HashMap<Integer, Integer>();
       int n=nums.length;
       int sum=0;
       int ret=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            ret+=hash.getOrDefault(sum-k,0);
            hash.put(sum,hash.getOrDefault(sum,0)+1);
        }
        return ret;
    }
    //和可被k整除的子数组
   /* 同余定理：
    (a-b)/p=k
    a-b=k*p
    a=k*p+b
    a%p=(k*p+b)%p
    a%p=b%p*/
   /*正负统一：
    a%p+p
    (a%p+p)%p*/
    public int subarraysDivByK(int[] nums, int k) {
        //哈希表里面放前缀和余数
          Map<Integer,Integer> hash=new HashMap<Integer,Integer>();
          int n=nums.length;
          int sum=0;
          int ret=0;
          //默认有一个前缀和为0
          hash.put(0,1);
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            int a=(sum%k+k)%k;
            ret+=hash.getOrDefault(a,0);
            hash.put(a, hash.getOrDefault(a,0)+1);
        }
        return ret;
    }
    //连续数组
    public int findMaxLength(int[] nums) {
          Map<Integer,Integer> hash=new HashMap<Integer,Integer>();
          int n=nums.length;
          hash.put(0,-1);
          int sum=0;
          int ret=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            if(nums[i]==0){
                sum-=1;
            }
          if(hash.containsKey(sum)){
              ret=Math.max(ret,i-hash.get(sum));
          }else {
              hash.put(sum,i);
          }
        }
        return ret;
    }
    //矩阵区域和
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int r=mat.length;
        int c=mat[0].length;
          int[][] dq=new int[r+1][c+1];
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                dq[i][j]=dq[i-1][j]+dq[i][j-1]+mat[i-1][j-1]-dq[i-1][j-1];
            }
        }
        int[][] ret=new int[r][c];
        for (int i = 0; i <r ; i++) {
            for (int j = 0; j < c; j++) {
                int x1=Math.max(0,i-k)+1;
                int y1=Math.max(0,j-k)+1;
                int x2=Math.min(r-1,i+k)+1;
                int y2=Math.min(c-1,j+k)+1;
                ret[i][j]=dq[x2][y2]-dq[x1-1][y2]-dq[x2][y1-1]+dq[x1-1][y1-1];
            }
        }
        return ret;
    }
    //二维分差

}
